即興LT: フルスクラッチRustで"世界"の創造主になる
https://scrapbox.io/files/6565cf9fc1d082001cf1ad2d.png
今回のLT
結構ライトです (5分ぐらいで終わる想定)
地形生成について
野望:架空の世界を生成したい
「地図帳の自動生成」
地形、交通網、地名などを自動生成する
最初のステップとして、地形生成に(3年間ぐらい)取り組んできた
そろそろ及第点が見えてきた
先行研究
MinecraftやOpenTTDは地形生成を使ったメディアの代表例
CG的アプローチ
「Generating fantasy maps」by Martin O'Leary
GitHub: https://github.com/mewo2/terrain
giganineの記事: https://gigazine.net/news/20160826-generating-fantasy-maps/ 
「Polygonal Map Generation for Games」by Amit Patel
http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/
地形学的アプローチ
数理モデルに基づいた地形の再現
河川の侵食作用に着目
地形形成の要因のほとんどは、侵食作用に基づいている
各地点に対して、侵食速度と隆起速度が釣り合う標高を反復的に求める
多くは SPIM(Stream Power Incusion Model) に基づいている
いろいろある
自分が最も参考にしたもの:
Guillaume Cordonnier, Jean Braun, Marie-Paule Cani, Bedrich Benes, Eric Galin, et al.. Large Scale Terrain Generation from Tectonic Uplift and Fluvial Erosion. Computer Graphics Forum, 2016, Proc. EUROGRAPHICS 2016, 35 (2), pp.165-175. ⟨10.1111/cgf.12820⟩. ⟨hal-01262376⟩
Pythonでは高度なシュミレータが存在
「badlands」https://github.com/badlands-model/badlands
地形をリアルに、高速に生成したい
ここで重要なのは見た目のリアルさで、地形学的に厳密であることは求められない
生成結果は高速に、かつ解析的に求まるものであって欲しい
純粋な地形学的アプローチでは割に合わない
かといって、CG的アプローチではリアルさに欠ける
地形学の要素を取り入れつつ、計算が手元環境で十分に間に合うものを作りたい
今作ってるやつ
"fastlem"
GitHub: https://github.com/TadaTeruki/fastlem
Web simulator: https://fastlem.peruki.dev/
ドキュメント作成中
開発はRustによる
メモリ管理やパフォーマンスを考える手間が省けそう
Web上でも処理できる(wasmビルド対応)
シュミレーションから描画まで、今の所ほとんど自力実装
一部アルゴリズムは既存パッケージに依存
生成の流れ
(1)点群データを生成
空間上にランダムに散りばめる
各点に対して、入力には侵食速度に関するパラメータ(例えば降水量、隆起速度)が、出力では標高が紐付けられる
(2) 河川を作成し、各点を結ぶ
隣り合っている点に対して、最も標高の下向き傾斜が大きい点に線を結び続ける
(3) 各点に対して流域面積を求め、入力パラメータに基づいて侵食速度を求める
(4) 侵食速度を標高へフィードバック
(5) (2)へ戻り、処理を繰り返す
標高が安定したら生成を終了
技術的側面
アルゴリズムの実装が多い
特に、空間情報の処理
ドロネー三角形分割 (ドロネー図の作成)
地形のデータは、空間上に散らばった点データ上でシュミレーション・マッピングされる
河川をシュミレーション・表現するには、点データ同士の繋がりをグラフで表現する必要がある
いい感じのグラフを作成するのに使うのがドロネー三角形分割
各地点の流域面積がSPIMパラメータの一つとなるが、それを求めるにはボロノイ図が必要
ドロネー図とボロノイ図は双対(どちらかがわかればどちらかが作れる)
補間
点データの存在しない場所のデータの値(標高など)を、周辺の点データから求めたい
キュービックスプラインなど1Dのものはよく知られているが、2Dになると実装が途端に難しくなる
Natural Neighbor Interpolation
https://github.com/TadaTeruki/naturalneighbor
点群中のデータを「自然に」補間する
描画時に使う
空間インデックス
空間データをいい感じに取り出す
R-treeなど
補間の高速化に使用 (与えられた点がどのドロネー三角形に重なっているかを調べる)
パーリンノイズ等のノイズジェネレーターも必要
入力パラメータを生成するため
乱数だと不都合なので、なめらかなノイズが必要
Procedural Generationは (自分の今までやってきた範囲だと) 空間情報のアルゴリズムのオンパレード
交通網生成にもなると、A*のような探索アルゴリズムや、L-systemも出てくる
たのしい(にっこり)